package q668_findKthNumber;

public class Solution_2 {
    public static void main(String[] args) {
        Solution_2 s = new Solution_2();
        s.findKthNumber(7,5,10);
    }
    /*
    实际上 这里唯一的区别在于
    count的初始化 显然 在有些行里面 整行的数字都是小于mid的
    这一行没有必要计算 所以我们可以把这些行先抽取出来加入到count中
    也就是初始 int count = x / n * n;
    也就是一开始有 mid/n 行的所有数字都小于 mid

    而此后的每一行都肯定无法取到n
    只需count += x / i;
     */
    public int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        while (left < right) {
            int x = left + (right - left) / 2;
            int count = x / n * n;
            for (int i = x / n + 1; i <= m; ++i) {
                count += x / i;
            }
            if (count >= k) {
                right = x;
            } else {
                left = x + 1;
            }
        }
        return left;
    }
}
